#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>

void MergeSort(int* arr, int start, int end)
{
	if (start >= end) return;

	int mid = (end - start) / 2 + start;
	int left = start, right = mid + 1;
	MergeSort(arr, start, mid);
	MergeSort(arr, mid + 1, end);
	std::vector<int> res;
	while (left <= mid || right <= end)
	{
		if (left > mid) res.push_back(arr[right++]);
		else if (right > end) res.push_back(arr[left++]);
		else
		{
			if (arr[right] > arr[left]) res.push_back(arr[left++]);
			else res.push_back(arr[right++]);
		}
	}
	int j = 0;
	for (int i = start; i <= end; i++)
	{
		arr[i] = res[j++];
	}
}

int main()
{
	int arr[10] = { 1, 6, 3, 5, 2, 7, 8, 9, 0, 4 };
	int n = sizeof(arr) / sizeof(arr[0]);
	for (auto e : arr) std::cout << e << ' '; std::cout << std::endl;
	MergeSort(arr, 0, n - 1);
	for (auto e : arr) std::cout << e << ' '; std::cout << std::endl;
	return 0;
}